package com.lwl.Algorithmic_data_structure.class10_11二叉树;

import com.lwl.Utils.MyTreeNode;

import java.util.LinkedList;

/**
 * @author lwl
 * @Description 找出树种宽度最大的一层，并且返回其宽度
 * @date 2023/5/24 7:44
 */
public class Code02TreeMaxWidth {

    public static int treeMaxWidth(MyTreeNode head) {
        if (head == null) {
            return 0;
        }
        int maxWidth = 0;
        MyTreeNode curEnd = head;
        MyTreeNode nextEnd = null;
        LinkedList<MyTreeNode> queue = new LinkedList<>();
        queue.addLast(head);
        curEnd = head;
        int curWidth = 0;
        while (!queue.isEmpty()) {
            MyTreeNode node = queue.pollFirst();
            if (node.left != null) {
                queue.addLast(node.left);
                nextEnd = node.left;
            }
            if (node.right != null) {
                queue.addLast(node.right);
                nextEnd = node.right;
            }
            curWidth++;
            // 换层
            if (node == curEnd) {
                curEnd = nextEnd;
                maxWidth = Math.max(maxWidth, curWidth);
                curWidth = 0;
            }
        }
        return maxWidth;
    }
}
